|
Lee introduced an algorithm for routing a two terminal net on a grid in 1961. Sine the, the basic algorithm has been improved for both speed and memory requirements. Lee's algorithm and its various improved version form the class of maze routing algorithms.
Maze routing are used to find a path between a pair of points, called the source(s) and the target(s), respectively, in a planar rectangular grid graph. The areas available for routing are represented as unblocked vertices, whereas, the obstacles are represented as blocked vertices. The objective of a maze routing algorithm is to find a path between the source and the target vertex without using any blocked vertex.
The process of finding a path begins with the exploration phase, in which several paths start at the source, and are expanded until one of them reaches the target. Once the target is reached, the vertices need to be retraced to the source to identify the path. The retrace phase can be easily implemented as long as the information about the parentage of each vertex is kept during the exploration phase. Several methods of path exploration have been developed.
Lee's Algorithm
This algorithm, which was developed by Lee in 1961, is the most widely used algorithm for finding a path between any two vertices on a planar rectangular grid. The key to the popularity of Lee's algorithm is its simplicity and its guarantee of finding an optimal solution if one exists.
The exploration phase of Lee's algorithm is an improved version of the
breadth-first search. The search can be visualized as a wave propagating from
the source.